#include <bits/stdc++.h>
using namespace std;
const int maxn = 20+5;
int M, N, K;
int d[maxn][maxn][maxn];
int G[maxn][maxn];
struct node{
    int r, c, k;
    explicit node(int r=0, int c=0, int k=0):r(r), c(c), k(k){}
};

int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};

inline bool in(int r, int c){
    return r>=1 && r<=M && c>=1 && c<=N;
}

void print(int ans){
    cout << ans << "\n";
}
void bfs(){
    queue<node> q;
    if(!G[1][1] || (G[1][1] && K)){
        node u(1, 1, 0);
        if(G[1][1]) u.k = 1;
        q.push(u);
        d[1][1][u.k] = 0;
    }

    while(!q.empty()){
        node u = q.front(); q.pop();
        if(u.r==M && u.c==N) {print(d[M][N][u.k]); return;}

        for (int i = 0; i < 4; ++i) {
            int r1 = u.r+dr[i], c1 = u.c+dc[i];
            if(in(r1, c1)){
                int k1 = G[r1][c1]? u.k+1 : 0;
                if(k1<=K && d[r1][c1][k1]<0){
                    node v(r1, c1, k1);
                    q.push(v);
                    d[r1][c1][k1] = d[u.r][u.c][u.k] + 1;
                }
            }
        }
    }
    print(-1);
}
void init(){
    memset(d, -1, sizeof(d));
    memset(G, 0, sizeof(G));
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int T; cin >> T;
    while(T--){
        cin >> M >> N >> K;
        init();
        for (int i = 1; i <= M; ++i) {
            for (int j = 1; j <= N; ++j) {
                cin >> G[i][j];
            }
        }
        bfs();
    }
    return 0;
}